home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / x2ftp / msdos / gamesrc / arasan_s / hash.h < prev    next >
C/C++ Source or Header  |  1994-07-15  |  3KB  |  131 lines
  1. // Copyright 1992 by Jon Dart.  All Rights Reserved.
  2.  
  3. #ifndef _HASH_H
  4. #define _HASH_H
  5.  
  6. #include "slist.h"
  7. #include <assert.h>
  8.  
  9. template <class Contents>
  10. class Hash
  11. {
  12.    // "generic" hash table class, stores entries of type "Contents".
  13.        
  14.    public:     
  15.  
  16.    Hash(const unsigned size, const unsigned long max_entries);
  17.    
  18.    ~Hash();
  19.  
  20.    Contents * search( const Contents &c );
  21.    // searches hash table for a position matching c
  22.  
  23.    void insert(const Contents &p);
  24.    // insert a new position in the hash table.
  25.        
  26.    void clear(Boolean final = False);       
  27.    // clear the hash table
  28.  
  29.    unsigned long num_entries() const;
  30.        
  31.    private:       
  32.     
  33.    unsigned my_size;
  34.    unsigned long my_max_entries;
  35.    S_List<Contents> **ht;
  36.    unsigned long hash_entries;
  37. };
  38.  
  39. #include <stddef.h>
  40.  
  41. template <class Contents>
  42. Hash<Contents>::Hash(const unsigned size, 
  43.     const unsigned long max_entries)
  44. {
  45.    my_size = size;
  46.    my_max_entries = max_entries;
  47.    hash_entries = 0L;
  48.    ht = new S_List<Contents> * [my_size];
  49.    assert(ht);
  50.    for (int i=0;i<my_size;i++)
  51.       ht[i] = NULL;
  52. }
  53.  
  54. template <class Contents>
  55. Hash<Contents>::~Hash()
  56. {
  57.    for (int i=0;i<my_size;i++)    
  58.    {
  59.       delete ht[i];
  60.    }
  61.    delete [] ht;
  62. }
  63.  
  64. template <class Contents>
  65. Contents * Hash<Contents>::search( const Contents &to_match )
  66. {
  67.     unsigned probe = (unsigned)(hash_code(to_match) % my_size);
  68.     S_List<Contents> *entry = ht[probe];
  69.     if (!entry)
  70.        return NULL;
  71.     entry->Rewind();
  72.     for (Contents *c = entry->Current(); c; c = entry->Next())
  73.     {
  74.        if (*c == to_match)
  75.           return c;
  76.     }
  77.     return NULL;
  78. }
  79.  
  80. template <class Contents>
  81. void Hash<Contents>::insert(const Contents &p)
  82. {
  83.     if (hash_entries >= my_max_entries)
  84.         return;
  85.     hash_entries++;
  86.     unsigned long h = hash_code(p);
  87.     unsigned probe = (unsigned)(h % my_size);
  88.     S_List<Contents> *entry = ht[probe];
  89.     if (!entry)
  90.     {
  91.        ht[probe] = new S_List<Contents>;
  92.        assert(ht[probe]);
  93.        ht[probe]->Insert(p);
  94.     }
  95.     else
  96.     {
  97.        entry->Rewind();        
  98.        Contents *c = entry->Current();
  99.        while (c)
  100.        {
  101.           if (*c == p)
  102.          return; // already in there
  103.       c = entry->Next();
  104.        }
  105.        entry->Insert(p);
  106.     }
  107. }
  108.  
  109. template <class Contents>
  110. void Hash<Contents>::clear(Boolean final)
  111. {
  112.    for (int i=0;i<my_size;i++)    
  113.    {
  114.       ht[i] = NULL;
  115.    }
  116.    // free all lists:
  117.    S_List<Contents>::freeAll(final);
  118.    // free all nodes:
  119.    S_Node<Contents>::freeAll(final);
  120.    hash_entries = 0;
  121. }
  122.  
  123. template <class Contents>
  124. unsigned long Hash<Contents>::num_entries() const
  125. {
  126.    return hash_entries;
  127. }
  128.  
  129. #endif
  130.  
  131.